package com.example.demo.leetcode.top;

/**
 * 快速排序
 * 思路:
 * 定义两个指针,i=0,j=arr.length
 * 初始值 temp = arr[0]
 * 从j开始向左  跟temp比较，如果小于temp,移到左边
 * 从i开始向右 跟temp比较 如果大于temo，移到右边
 * 最终 i，j重合, 把temp的值给重合点。
 * 将重合点的左右两边重复上述过程->递归(结束条件:当前集合大小为1)
 * 其实快速排序的本质就是把基准数大的都放在基准数的右边,把比基准数小的放在基准数的左边,这样就找到了该数据在数组中的正确位置.
 *
 */
public class Array_快速排序 {


    public static void quicklySort(int [] arr){
        quickyDiguiSort(arr,0,arr.length-1);
    }


    //复习快排
    public static void quickyDiguiSort(int [] arr,int start,int end){

        int i = start;
        int j = end;
        int temp = arr[start];
        if(i>=j){
            return;
        }
        while(i<j){
            //从右往左遍历
            while(i<j && arr[j]>temp){
                j--;
            }
            if(i<j){
                //替换后 i++
                arr[i] = arr[j];
                i++;
            }

            //从左往右遍历
            while(i<j && arr[i]<temp){
                i++;
            }
            if(i<j){
                //替换后j--
                arr[j] = arr[i];
                j--;
            }
        }
        //temp给重合点
        arr[i]=temp;
        //注意边界
        for(int k=0;k<arr.length;k++){
            System.out.print(arr[k]+" ");
        }
        System.out.println();
        quickyDiguiSort(arr,start,i-1);
        quickyDiguiSort(arr,i+1,end);
    }

    public static void main(String[] args) {
        int [] arr = {7,12,5,1,6,2,15};
        quicklySort(arr);
        for(int i =0 ;i<arr.length;i++){
            System.out.print(arr[i]+" ");
        }

    }


}
